A cache memory is a high-speed storage mechanism that stores copies of data and/or instructions from a main memory. When a central processing unit (CPU) intends to read/write data from/into a location in the main memory, it first determines whether the location is in the cache memory, because the cache memory provides faster access to the data therein. For example, if the CPU is executing a read request, the CPU will check the cache memory to see if the data is in the cache memory. If the data is located in the cache memory (“a cache hit”), the CPU immediately reads the data from the cache memory. However, if the data is not in the cache memory (“a cache miss”), the data needs to be copied from the main memory to a location in the cache memory. This copying of data from the main memory to the cache memory is termed a “cache fill,” i.e., data is filled into the cache memory from the main memory. The cache fill operation may fill an empty location (referred to as a “cache line”) in the cache memory if any cache lines are available. However, if there are no empty cache lines, then an existing cache line needs to be replaced with the new data from main memory. In this manner, the data will be readily accessible when the location is subsequently referenced. However, the cache miss incurs a delay in retrieval/write time, because the cache fill operation needs to be performed, thereby making access to data and/or instructions in the main memory slower than access to data and/or instructions that are already stored in the cache memory.
Ideally, when the CPU executes a program, it will attempt to store the entire program in the cache memory. However, this is impractical, because the cache memory is limited in size and usually smaller than the program. Thus, the program is stored in the larger random access memory (RAM) or virtual memory. As a result, data and instruction sections of the program map to similar cache lines. This causes cache collisions. For example, when a memory location is referenced in the program, the CPU first attempts to find it in the cache memory. However, the cache memory may not contain the location (i.e., a cache miss), so another line must be purged from the cache memory to make room for a new cache line which includes the missing data. Cache collisions and cache misses prevent the CPU from realizing a full performance potential of the cache memory. While most program optimization strategies deal with a replacement policy utilized by the cache memory (i.e., determining which cache line is purged to make room for the new cache line), there has not been any attempt to manipulate data or instruction memory to reduce cache misses or cache collisions in the cache memory.